package algorithms.a06unionfind;

import com.google.common.base.Preconditions;

/**
 * 并查集 第一版简化版
 * 并查集只能解决一个网络中，各个点之间是否有联系，而无法解决联系的路径问题
 * @author 王昊然
 * @create 2018-02-23 9:13
 **/
public class UnionFind1 {

    private int[] ids;
    private int count;

    public UnionFind1(int n) {
        ids = new int[n];
        count = n;

        for (int i = 0; i < n; i++) {
            ids[i] = i;
        }
    }

    /**
     * 查找
     * p是元素下标
     *
     * @param p
     * @return
     */
    public int find(int p) {
        Preconditions.checkArgument(p < count, "p超出集合范围");

        return ids[p];
    }

    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    public void unionElements(int p, int q) {

        int idp = find(p);
        int idq = find(q);

        if(idp == idq) return;

        for (int i = 0; i < count; i++) {
            if(ids[i] == idq){
                ids[i] = idp;
            }
        }
    }

    // 测试UF1
    public static void main(String[] args) {

        // 使用10000的数据规模
        int n = 100000;

        // 虽然isConnected只需要O(1)的时间, 但由于union操作需要O(n)的时间
        // 总体测试过程的算法复杂度是O(n^2)的
        UnionFindTestHelper.testUF1(n);
    }
}
